/*
 * Copyright (C), 2015-2018
 * FileName: Solution160
 * Author:   zhao
 * Date:     2018/9/14 19:53
 * Description: 160. 相交链表
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈160. 相交链表〉
 *
 * @author zhao
 * @date 2018/9/14 19:53
 * @since 1.0.1
 */
public class Solution160 {

  /**************************************
   * 题目
   编写一个程序，找到两个单链表相交的起始节点。

   例如，下面的两个链表：

   //   A:          a1 → a2
   //                                 ↘
   //                                 c1 → c2 → c3
   //                                 ↗
   //   B:     b1 → b2 → b3
   在节点 c1 开始相交。

   注意：
   如果两个链表没有交点，返回 null.
   在返回结果后，两个链表仍须保持原有的结构。
   可假定整个链表结构中没有循环。
   程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
   **************************************/

  /**************************************
   *
   * 想法：
   *      先判断2个链表的最后一个数据是不是相同的，是-->有交叉，不是-->没有交叉
   *      获取2条链表各自的长度
   *
   *      看题目这张图片，需要将AB链表从短链表的首个内容进行遍历
   *    A:          a1 → a2
   *                                 ↘
   *                                 c1 → c2 → c3
   *                                  ↗
   *    B:     b1 → b2 → b3
   *    循环长度，
   *        当AB的count值不同时进行加减
   *        相同时就进行比较
   *
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *      这题没想出来，
   *      很多链表类的问题可以使用双指针法
   *
   *
   * ***********************************/
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
      return null;
    }

    // 下面判断最后一个是否相同，并且记录总数
    ListNode lastA = headA;
    int countA = 1;
    while (lastA.next != null) {
      lastA = lastA.next;
      countA++;
    }
    ListNode lastB = headB;
    int countB = 1;
    while (lastB.next != null) {
      lastB = lastB.next;
      countB++;
    }
    if (!lastA.equals(lastB)) {
      return null;
    }

    ListNode tmpA = headA;
    ListNode tmpB = headB;
    while (countA > 0 && countB > 0) {
      if (tmpA.equals(tmpB)) {
        return tmpA;
      }
      if (countB == countA) {
        countA--;
        countB--;
        tmpA = tmpA.next;
        tmpB = tmpB.next;

      } else if (countB < countA) {
        countA--;
        tmpA = tmpA.next;
      } else {
        countB--;
        tmpB = tmpB.next;
      }
    }

    return null;
  }

  /**
   * 这个思路就是 ListA + ListB = A + intersection + Bb + intersection
   * ListB + ListA = Bb + intersection + A + intersection
   * 用大A表示ListA里面非共有 Bb表示listB里面非共有的，可以看到在第二个intersection的开头两个链表长度是一样的，必然相等
   * 所以我们可以遍历A再遍历B，另一个遍历B再遍历A，两个指针必定在第二个交集处相遇，没有交集就是空指针
   **/
  public ListNode better(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
      return null;
    }
    ListNode l1 = headA, l2 = headB;
    while (l1 != l2) {
      l1 = (l1 == null ? headB : l1.next);
      l2 = (l2 == null ? headA : l2.next);
    }
    return l1;
  }
}
